import java.util.Arrays;

class Solution5 {
    public static int[][] matrixBlockSum(int[][] mat, int k) {
        int n = mat.length;
        int[][] dp = new int[n+1][mat[0].length+1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= mat[0].length; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1] + mat[i-1][j-1] -dp[i-1][j-1];
            }
        }
        int[][] answer = new int[n][mat[0].length];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < mat[0].length; j++) {
                int x1 = Math.max(0,i-k)+1;
                int y1 = Math.max(0,j-k)+1;
                int x2 = Math.min(n-1,i+k)+1;
                int y2 = Math.min(mat[0].length-1,j+k)+1;
                answer[i][j] = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        int[][] array = {{67,64,78},{99,98,38},{82,46,46},{6,52,55},{55,99,45}};
        int[][] answer = new int[5][3];
        answer = matrixBlockSum(array,3);
        System.out.println(Arrays.toString(answer));
    }
}